package DataStructures.BinaryTree;

import java.util.Arrays;

/**
 * @author ：ALi
 * @date ：Created in 2021/12/10 19:31
 * @description：堆排序
 * @modified By：
 * @version: $
 */
public class HeapsortTest {
    public static void main(String[] args) {
        int[] array = {50, 10, 90, 30, 70, 40, 80, 60, 20};
        int temp = 0;
        //变为大顶堆
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            Heapsort(array, i, array.length);
        }

        //将大顶堆的头节点和最后的节点交换，将最大的数都放到最后，再次堆排序，此次堆排序的长度-1，
        //排序完成后就得到了从小到大的数组
        for (int i = array.length - 1; i > 0; i--) {
            temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            Heapsort(array, 0, i);

        }
        System.out.println(Arrays.toString(array));
    }

    /**
     * 数组下标从0开始，若下标为i，则其左孩子下标为i*2+1；右孩子是i*2+2；
     *
     * @param array  数组
     * @param start  其实节点位置
     * @param length 数组长度（二叉树节点个数）
     */
    public static void Heapsort(int[] array, int start, int length) {
        int temp = array[start];
        for (int i = 2 * start + 1; i < length; i = i * 2 + 1) {
            //在两个节点中找到最大一个和其父节点交换。
            if (i + 1 < length && array[i] < array[i + 1]) {
                i++;
            }
            if (array[i] > temp) {
                //交换两个元素。将最大元素放到父节点处。
                temp = array[start];
                array[start] = array[i];
                array[i] = temp;
                //将当前节点位置移动到交换顺序的节点处，查看其交换后，其子节点是否还是完全二叉树，这也就是为什么i=i*2+1。
                // 没有交换的节点其还是完全二叉树
                start = i;
            } else {
                break;
            }
        }
    }


}